LeetCode 394.Decode String

LeetCode新题

LeetCode最近好像又更新了，之前刷了100道左右的Easy和Medium，但是之前刷的题都没有写博客，这次写是因为网上的解法还很少，所以发上来供大家查阅。

题意和解法

这道题的题意其实很简单，就不过多解释了，看到此类表达式的计算，我们第一个想到的数据结构就是栈，利用栈的先进后出性质进行计算。

过程

遍历字符串，遇到数字、字母和[直接进栈，遇到]，然后出栈，先找出所有字母，直到[(也要出栈)，然后再继续出栈找出数字，这里注意数字可能是多位的，比如123[a]，所以出栈的终止条件是栈空或者遇到非数字的字符，通过上面出栈的字符串和数字，组成新的字符串，如字符串2[ab]，新的字符串应该为abab，这些新的字符也必须再重新进栈。就这么简单~

AC代码

第一版代码，后面如果优化了会再更新

public static String decodeString(String s) {
    if (s == null || s.length() == 0)
        return s;
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == ']') {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty() && ((stack.peek() >= 'a' && stack.peek() <= 'z') || stack.peek() == '[')) {
                char ccc = stack.pop();
                if (ccc == '[')
                    break;
                sb.insert(0, ccc);
            }
            if (stack.isEmpty()) {
                return sb.toString();
            } else {
                int count = 0;
                int w = 1;
                while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
                    int val = stack.pop() - '0';
                    count += val * w;
                    w *= 10;
                }
                char[] chars = sb.toString().toCharArray();
                while (count > 0) {
                    for (char cc : chars)
                        stack.push(cc);
                    count--;
                }
            }
        } else
            stack.push(c);
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty())
        sb.insert(0, stack.pop());
    return sb.toString();
}